home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Hacks / Hacks ’97 / Warrior’s Progress / source code / Source / Libraries / Trees / Tree.cp < prev    next >
Encoding:
Text File  |  1997-06-28  |  2.3 KB  |  142 lines  |  [TEXT/CWIE]
  1. // Tree.cp
  2.  
  3. #ifndef Tree_h
  4. #include "Tree.h"
  5. #endif
  6. #ifndef TreeNode_h
  7. #include "TreeNode.h"
  8. #endif
  9.  
  10. Tree::Tree()
  11.   : root( 0 )
  12.   {
  13.   }
  14.  
  15. Tree::~Tree()
  16.   {
  17.     Assert( IsEmpty() );
  18.   }
  19.  
  20. void Tree::Add( TreeNode& toAdd, AtRoot )
  21.   {
  22.     Assert( toAdd.tree == 0 );
  23.     Assert( toAdd.left == 0 );
  24.     Assert( toAdd.right == 0 );
  25.     Assert( toAdd.parent == 0 );
  26.     
  27.     Assert( root == 0 );
  28.     
  29.     WillAdd( toAdd, after, 0 );
  30.     
  31.     toAdd.tree = this;
  32.     root = &toAdd;
  33.   }
  34.  
  35. void Tree::Add( TreeNode& toAdd, Before, const TreeNode& next )
  36.   {
  37.     Assert( toAdd.tree == 0 );
  38.     Assert( toAdd.left == 0 );
  39.     Assert( toAdd.right == 0 );
  40.     Assert( toAdd.parent == 0 );
  41.     
  42.     Assert( next.tree == this );
  43.     Assert( next.left == 0 );
  44.     
  45.     WillAdd( toAdd, before, &next );
  46.     
  47.     TreeNode& mutableNext( const_cast<TreeNode&>( next ) );
  48.     
  49.     toAdd.tree = this;
  50.     mutableNext.left = &toAdd;
  51.     toAdd.parent = &mutableNext;
  52.   }
  53.  
  54. void Tree::Add( TreeNode& toAdd, After, const TreeNode& previous )
  55.   {
  56.     Assert( toAdd.tree == 0 );
  57.     Assert( toAdd.left == 0 );
  58.     Assert( toAdd.right == 0 );
  59.     Assert( toAdd.parent == 0 );
  60.     
  61.     Assert( previous.tree == this );
  62.     Assert( previous.right == 0 );
  63.     
  64.     WillAdd( toAdd, after, &previous );
  65.  
  66.     TreeNode& mutablePrevious( const_cast<TreeNode&>( previous ) );
  67.     
  68.     toAdd.tree = this;
  69.     mutablePrevious.right = &toAdd;
  70.     toAdd.parent = &mutablePrevious;
  71.   }
  72.  
  73. void Tree::Remove( TreeNode& toRemove )
  74.   {
  75.     Assert( toRemove.tree == this );
  76.     Assert( toRemove.left == 0 );
  77.     Assert( toRemove.right == 0 );
  78.     
  79.     WillRemove( toRemove );
  80.     
  81.     toRemove.LinkFromAbove() = 0;
  82.     toRemove.parent = 0;
  83.     toRemove.tree = 0;
  84.   }
  85.  
  86. void Tree::RemoveAll()
  87.   {
  88.     TreeNode *n = root;
  89.     
  90.     while ( n != 0 )
  91.       {
  92.         if ( n->left != 0 )
  93.             n = n->left;
  94.          else if ( n->right != 0 )
  95.              n = n->right;
  96.          else
  97.           {
  98.             TreeNode& toRemove( *n );
  99.             n = n->parent;
  100.             Remove( toRemove );
  101.           }
  102.       }
  103.   }
  104.  
  105. TreeNode *Tree::FirstNode() const
  106.   {
  107.     if ( root == 0 )
  108.         return 0;
  109.     
  110.     TreeNode *n = root;
  111.     while ( n->left != 0 )
  112.         n = n->left;
  113.     
  114.     return n;
  115.   }
  116.  
  117. TreeNode *Tree::LastNode() const
  118.   {
  119.     if ( root == 0 )
  120.         return 0;
  121.     
  122.     TreeNode *n = root;
  123.     while ( n->right != 0 )
  124.         n = n->right;
  125.     
  126.     return n;
  127.   }
  128.  
  129. bool Tree::Valid() const
  130.   {
  131.     if ( root != 0 && root->parent != 0 )
  132.         return false;
  133.     
  134.     for ( const TreeNode *n = First(); n != 0; n = n->Next() )
  135.         if ( !n->Valid() )
  136.             return false;
  137.     
  138.     return true;
  139.   }
  140.  
  141. #include "Sequence.cp"
  142.